package 中等.滑动窗口;

/**
 * 给你两个字符串 word1 和 word2 。
 * 如果一个字符串 x 重新排列后，word2 是重排字符串的
 * 前缀，那么我们称字符串 x 是 合法的 。
 * 请你返回 word1 中 合法
 * 子字符串
 * 的数目。
 *
 * @ https://leetcode.cn/problems/count-substrings-that-can-be-rearranged-to-contain-a-string-i/description/?envType=daily-question&envId=2025-01-09
 * @date 2025/01/10
 */
public class 统计重新排列后包含另一个字符串的子字符串数目I_3297 {

    public static void main(String[] args) {

    }

    public long validSubstringCount(String word1, String word2) {
        long ans = 0;
        int[] cnt2 = new int[26];
        for (char c : word2.toCharArray()) {
            cnt2[c - 'a']++;
        }

        int[] cnt1 = new int[26];
        int left = 0, right = 0;
        while (left < word1.length()) {
            while (right < word1.length() && compare(cnt1, cnt2) < 0) {
                cnt1[word1.charAt(right) - 'a']++;
                right++;
            }
            if (compare(cnt1, cnt2) == 0) {
                ans += word1.length() - right + 1;
            }
            cnt1[word1.charAt(left) - 'a']--;
            left++;
        }
        return ans;
    }

    // 只要 cnt1 中有一个数字 < cnt2 中对应的数字，返回-1
    private int compare(int[] cnt1, int[] cnt2) {
        for (int i = 0; i < cnt1.length; i++) {
            if (cnt1[i] < cnt2[i]) {
                return -1;
            }
        }
        return 0;
    }

}
